//有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，
//5，7，9，15，21。 
//
// 示例 1: 
//
// 输入: k = 5
//
//输出: 9
// 
// Related Topics哈希表 | 数学 | 动态规划 | 堆（优先队列） 
//
// 👍 186, 👎 0 
//
//
//
//

package leetcode.editor.day;

// 面试题 17.09. 第 k 个数
// https://leetcode.cn/problems/get-kth-magic-number-lcci/
class GetKthMagicNumberLcci {
    public static void main(String[] args) {
        Solution solution = new GetKthMagicNumberLcci().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // https://leetcode.cn/problems/get-kth-magic-number-lcci/solution/di-k-ge-shu-by-leetcode-solution-vzp7/
    class Solution {
        // 堆（注意溢出）
        /*public int getKthMagicNumber(int k) {
            int[] factor = {3, 5, 7};
            int res = 0;
            PriorityQueue<Long> queue = new PriorityQueue<>();
            Set<Long> set = new HashSet<>();
            queue.offer(1L);
            set.add(1L);

            for (int i = 0; i < k; i++) {
                long cur = queue.poll();
                res = (int) cur;
                for (int f : factor) {
                    long val = f * cur;
                    if (!set.contains(val)) {
                        queue.offer(val);
                        set.add(val);
                    }
                }
            }

            return res;
        }*/

        // DP
        public int getKthMagicNumber(int k) {
            int[] dp = new int[k + 1];
            dp[1] = 1;
            int p3 = 1, p5 = 1, p7 = 1;
            for (int i = 2; i <= k; i++) {
                int num3 = dp[p3] * 3, num5 = dp[p5] * 5, num7 = dp[p7] * 7;
                dp[i] = Math.min(num3, Math.min(num5,num7));
                if (num3 == dp[i]) {
                    p3++;
                }

                if (num5 == dp[i]) {
                    p5++;
                }

                if (num7 == dp[i]) {
                    p7++;
                }
            }

            return dp[k];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
